หนังสือคู่มือ C++ เวอร์ชันที่ 5: ข้ามการค้นหาแบบเส้นตรง: พลังของคอนเทนเนอร์เชิงความสัมพันธ์

ลองนึกภาพห้องสมุดที่หนังสือไม่ได้จัดเรียงตามวันที่มาถึง แต่จัดโดยใช้ กุญแจสากลซึ่งเป็นการเปลี่ยนแปลงแนวคิดจากแบบลำดับไปยัง คอนเทนเนอร์เชิงความสัมพันธ์แทนที่จะสแกน เวกเตอร์ แบบเส้นตรง ($O(N)$) เราจะใช้ แมป หรือ เซต เพื่อให้การค้นหาใช้เวลาลอการิธึม ($O(\log n)$)

1. ธรรมชาติของการเชื่อมโยง

ใน แมปเราเก็บข้อมูล คู่คีย์-ค่าคีย์ทำหน้าที่เป็นดัชนี ซึ่งสามารถเป็นสตริง วัตถุผู้ใช้กำหนด หรือประเภทใด ๆ ที่รองรับ การจัดเรียงอย่างเข้มงวดและ เซตกลับกัน เก็บเฉพาะคีย์ที่ไม่ซ้ำกัน จึงเหมาะสำหรับการตรวจสอบสมาชิกหรือกรองข้อมูล

2. แบบเรียงลำดับกับแบบไม่เรียงลำดับ

คอนเทนเนอร์มาตรฐาน (แมป, เซต) จะจัดเรียงคีย์ให้อยู่ตามลำดับ ตามมาตรฐานภาษา C++11 ได้แนะนำเวอร์ชันที่ไม่เรียงลำดับ (unordered_map) ที่ใช้ฟังก์ชันแฮช ฟังก์ชันแฮช เพื่อประสิทธิภาพเฉลี่ย $O(1)$ มองหา โลโก้ C++11 เมื่อใช้งานบักเก็ตประสิทธิภาพสูงเหล่านี้

TERMINALbash — 80x24

> Ready. Click "Run" to execute.

QUESTION 1

What happens when you use the subscript operator m[k] on a map if the key k does not exist?

It throws an out_of_range exception.

It returns a null pointer.

It adds a new element with key k and a value-initialized value.

The program fails to compile.

❌ Incorrect

Unlike at(), the [] operator is an insertion-on-demand mechanism.

QUESTION 2

Which of the following calls is ILLEGAL for a multiset c and a vector v?

copy(v.begin(), v.end(), inserter(c, c.end()));

copy(v.begin(), v.end(), back_inserter(c));

copy(c.begin(), c.end(), back_inserter(v));

copy(c.begin(), c.end(), inserter(v, v.end()));

✅ Correct!

Correct. back_inserter requires push_back, which associative containers like multiset do not support.

❌ Incorrect

Associative containers lack push_back, so back_inserter cannot be used with them.

QUESTION 3

Identify the correct way to define a variable to hold the result of calling find on a map<string, vector>>.

vector<int> res = m.find("key");

map<string, vector>::iterator it = m.find("key");>

pair<string, vector> p = m.find("key");>

bool found = m.find("key");

✅ Correct!

find returns an iterator to the element if found, or m.end() otherwise.

❌ Incorrect

The find method always returns an iterator, not the value or a boolean.

QUESTION 4

What is the primary advantage of using a set over a vector for storing a list of excluded words?

A set uses less memory than a vector.

A set allows for duplicate excluded words.

A set provides O(log N) lookup instead of O(N) linear search.

A set allows elements to be accessed by index.

✅ Correct!

Using exclude.find(word) on a set is significantly more efficient than std::find on a vector for large datasets.

QUESTION 5

In the expression ++word_count.insert({word, 0}).first->second;, what does first refer to?

The key of the inserted element.

The boolean indicating if insertion was successful.

An iterator to the element with the given key.

The first element in the entire map.

✅ Correct!

map::insert returns a pair where first is an iterator to the element.

❌ Incorrect

The return of insert is a pair<iterator, bool>. first is the iterator.